package 代码随想录.栈与队列;

import java.util.ArrayDeque;
import java.util.ArrayList;

public class _6滑动窗口最大值 {
    /**
     * 239. 滑动窗口最大值
     * https://leetcode.cn/problems/sliding-window-maximum/
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(k>0 && k<=nums.length){
            ArrayDeque<Integer> dq = new ArrayDeque<>();
            for(int i=0;i<k;i++){
                while (!dq.isEmpty() && nums[dq.peekLast()]<nums[i])
                    dq.pollLast();
                dq.offerLast(i);
            }
            for(int i=k;i<nums.length;i++){
                res.add(nums[dq.peekFirst()]);
                while (!dq.isEmpty()&&dq.peekFirst()<(i-k+1))
                    dq.pollFirst();
                while (!dq.isEmpty() && nums[dq.peekLast()]<nums[i])
                    dq.pollLast();
                dq.offerLast(i);
            }
            res.add(nums[dq.pollFirst()]);
        }
        if(res.isEmpty())
            return new int[0];
        return res.stream().mapToInt(x->x).toArray();
    }
}
